package backtrack;

import java.util.ArrayList;
import java.util.List;

public class Solution_22 {

    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        StringBuilder path = new StringBuilder();
        dfs(0, 0, n, path);
        return res;
    }

    /**
     * 这段代码很明显的展示了三个约束条件：
     * 1、左括号必须出现对应右括号的左边
     * 2、左括号的个数不能超过n
     * 3、右括号的个数不能超过左括号
     */
    private void dfs(int left, int right, int n, StringBuilder path) {
        if (path.length() == 2 * n) {
            res.add(path.toString());
            return;
        }
        if (left < n) {
            path.append('(');
            dfs(left + 1, right, n, path);
            path.deleteCharAt(path.length() - 1);
        }
        if (right < left) {
            path.append(')');
            dfs(left, right + 1, n, path);
            path.deleteCharAt(path.length() - 1);
        }
    }


    public static void main(String[] args) {
        Solution_22 solution22 = new Solution_22();
        System.out.println(solution22.generateParenthesis(3));
    }
}
